# 来自 err0rzz 的博客：https://err0rzz.github.io/2017/11/14/CTF%E4%B8%ADRSA%E5%A5%97%E8%B7%AF/

# n=0x78e2e04bdc50ea0b297fe9228f825543f2ee0ed4c0ad94b6198b672c3b005408fd8330c36f55d36fb129d308c23e5cb8f4d61aa7b058c23607cef83d63c4ed0f066fc0b3c0062a2ac68c75ca8035b3bd7a320bdf29cfcf6cc30377743d2a8cc29f7c588b8043412366ab69ec824309cb1ef3851d4fb14a1f0a58e4a1193f5518fa1d0c159621e1f832b474182593db2352ef05101bf367865ad26efe14fce977e9e48d3310a18b67991958d1a01bd0f3276a669866f4deaef2a68bfaefd35fe2ba5023a22c32ae8b2979c26923ee3f855363f18d8d58bb1bc3b7f585c9d9f6618c727f0f7b9e6f32af2864a77402803011874ed2c65545ced72b183f5c55d4d1
# e=0x10001
# nextprime(p)*nextprime(q)=0x78e2e04bdc50ea0b297fe9228f825543f2ee0ed4c0ad94b6198b672c3b005408fd8330c36f55d36fb129d308c23e5cb8f4d61aa7b058c23607cef83d63c4ed0f066fc0b3c0062a2ac68c75ca8035b3bd7a320bdf29cfcf6cc30377743d2a8cc29f7c588b8043412366ab69ec824309cb1ef3851d4fb14a1f0a58e4a1193f5a58ee70a59ac06b64dbe04b876ff69436b78cf03371f2062707897bf4e580870e42b5e62709b69f6d4939ac5641ea0f29de44aaee8f2fcd0f66aaa720b584f7c801e52ce7cd41db45ceb99ebd7b51bef8d0cd2deb5c50b59f168276c9c98d46a1c37bd3d6ef81f2c6e89028680a172e00d92dd8b392135112dd16efab57d00b26b9
# c=0x1c3588ac81ec3d1b439cfd2d5e6e8a5a95c8f95aaeff1b0ba49276ade80435323f307a17006ae2ffb4ca321e54387d9b33ed7ccda3117f7bc8d247ffd2ccdd67b7e2aad3d908d0a5187a73d13d532c1cf41758e2743bd4359bf72a99bbf0d716bb171cf636bd56acee9551cbb8af25f32583facbd25aed232659d24580c5a30a080e2860790a65422f7c442559c3042d37fdd7e8c1dd604252a2cbff8c74e5a0b6a0dfb9dcfed9eed515705ab9214dcf2dabce7b354040940613d065918079b3197da948b6d1d7daccc417069f7102fd2525e879fe69b6d5fb39e1dd6c0a9a9087dcc809294d7774efb42829f6124dff4af44f308977d1f91422c63073176026

"""
n = p * q
nn = p1 * q1

因为 p*q1 和 q*p1 应该是接近的
直接用 yafu 分解 n*nn
得到 p*q1 和 q*p1

分别与 n (= p*q) 求公约数
得到 p, q
"""
